package leetcode.搜索;

/**
 * 搜索旋转排序数组
 */
public class Test33搜索旋转排序数组 {

    /**
     * 二分搜索
     *
     * @param nums   旋转数组 [4,5,6,7,0,1,2]
     * @param target 目标值
     * @return
     */
    public static int search(int[] nums, int target) {
        if (nums.length == 0)
            return -1;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > nums[right]) { // 这一句只能区分出mid之前的为大序列，且有序。mid之后的是小序列，不一定有序
                // 然后再判断 target 处于哪一个区间
                if (nums[left] <= target && nums[mid] > target)
                    // 两个条件一组合说明target一定在大序列里面
                    right = mid - 1;
                else
                    left = mid + 1;
            } else {
                if (nums[right] >= target && nums[mid] < target)
                    // 这两个条件说明target一定在小序列里面
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return -1;
    }

    public static int search2(int[] nums, int target) {
        int ans = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                ans = i;
            } else {
                continue;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int target = 0;
        System.out.println(search(nums, target));
    }
}
